package com.heyqing.greedy;
import java.util.ArrayList;

import java.util.List;
/**
 * ClassName:ActivitySelector
 * Package:com.heyqing.greedy
 * Description:
 *  排序方法
 * @Date:2024/5/27
 * @Author:Heyqing
 */
public class ActivitySelector {
    // 找出最大的相容活动子集
    List<Activity> findMaximalCompatibleSubset(Activity[] activities) {
        // 先按结束时间排序
        quickSort(activities, 0, activities.length - 1);
        List<Activity> result = new ArrayList<>();
        if (activities.length > 0) {
            result.add(activities[0]); // 第一个活动总是被选中
            int lastIndex = 0; // 最后一个被选中的活动的索引
            for (int i = 1; i < activities.length; i++) {
                // 如果当前活动的开始时间大于等于上一个被选中活动的结束时间
                if (activities[i].start >= activities[lastIndex].finish) {
                    result.add(activities[i]); // 则加入结果集
                    lastIndex = i; // 更新最后一个被选中活动的索引
                }
            }
        }
        return result;
    }

    /**
     * 快速排序算法
     * 1、递归排序
     * 2、接收一个Activity的数组，以及需要排序的左右索引
     * 3、if left < right 会调用partition选择一个基准
     *      l:所有元素小于等于基准
     *      r:所有元素大于基准
     * @param arr
     * @param left
     * @param right
     */
    void quickSort(Activity[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            //左部分
            quickSort(arr, left, pivotIndex - 1);
            //右部分
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    /**
     * 选择一个基准
     * @param arr
     * @param left
     * @param right
     * @return
     */
    int partition(Activity[] arr, int left, int right) {
        Activity pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j].compareTo(pivot) <= 0) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }

    /**
     * 交换元素
     * @param arr
     * @param i
     * @param j
     */
    void swap(Activity[] arr, int i, int j) {
        Activity temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
